#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     int flag;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr), flag(0) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };


vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    s.push(root);
    while(s.top())
    {
        cur = s.top();
        //若栈顶节点的值为0，则将其值置为1并且依次将左节点、该节点、右节点的值入栈
        if(cur->flag==0)
        {
            //此为中序遍历的顺序，先右节点入栈，然后再将左节点入栈；若是前序或者是后序需要做修改
            if(cur->right)
                s.push(cur->right);
            cur->flag=1;
            if(cur->left)
                s.push(cur->left);
        }
        //若节点的值不为0，则将其值输出并且出栈
        else
        {
            res.push_back(cur->val);
            s.pop();
        }           
    }
    return res;
}
int main()
{
    vector<int> v={1,-1,2,3};
    TreeNode* root = new TreeNode(0);
    TreeNode* cur = root;
    int i = 0;
    cur->val = v[i++];
    cur->right = new TreeNode(v[i+2]);
    cur = cur->right;
    cur->left = new TreeNode(v[i++]);
    vector<int> result= inorderTraversal(root);
    for(auto x:result)
    {
        cout<<x<<" ";
    }
    return 0;
}